package mianshi;

/**
 * description:
 * author:zt
 * date:2021-08-06
 */

/**
 * 编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。
 *
 * 待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。
 *
 * 「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。
 *
 * 请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。
 */
public class _08_10 {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (newColor == image[sr][sc]) return image;
        dfs(image,sr,sc,newColor,image[sr][sc]);
        return image;
    }
    public void dfs(int[][] image,int sr,int sc,int newColor,int oldColor){
        //越界或者这个点不能涂就返回
        if(sr < 0 || sr >= image.length || sc < 0 || sc >= image[sr].length || image[sr][sc] != oldColor)
            return;
        //涂色+四个方向扩散
        image[sr][sc] = newColor;
        dfs(image, sr - 1, sc, newColor, oldColor);
        dfs(image, sr + 1, sc, newColor, oldColor);
        dfs(image, sr , sc - 1, newColor, oldColor);
        dfs(image, sr , sc + 1, newColor, oldColor);
    }

}
